package com.company.ljh.medium;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @description:
 * 1926. 迷宫中离入口最近的出口
 * 提示
 * 中等
 * 51
 * 相关企业
 * 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
 *
 * 每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
 *
 * 请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/6 14:57
 * @version:1.0
 */
public class 迷宫中离入口最近的出口 {

    public int nearestExit(char[][] maze, int[] entrance) {
        int []result = new int[1];
        Bfs(maze,result,entrance);
        return result[0];
    }
    //**注意：在入队之前将节点设置为已访问状态，防止同一个节点多次入队
    public void Bfs(char[][] maze,int[] result,int[]entrance){
        int distince = -1;
        //广度优先遍历，第一个遍历到终点的节点即为最短路径
        Queue<int[]> queue = new LinkedList();
        queue.offer(entrance);
        //变墙标记访问
        maze[entrance[0]][entrance[1]] = '+';
        while(!queue.isEmpty()){
            int n = queue.size();
            distince++;
            for(int i=0;i<n;i++){
                int[] thisNode = queue.poll();
                int x = thisNode[0];
                int y = thisNode[1];
                if(distince !=0 &&checkIsExit(maze,x,y)){
                    //第一次找到出口，循环结束
                    result[0] = distince;
                    return;
                }
                if(x != 0 &&maze[x-1][y] == '.'){
                    //查找上边
                    queue.offer(new int[]{x-1,y});
                    //提前将已加入队列的标记为访问状态，防止同一个位置重复添加至队列
                    maze[x-1][y] = '+';
                }
                if(x != maze.length-1&&maze[x+1][y] == '.'){
                    //查找下边
                    queue.offer(new int[]{x+1,y});
                    maze[x+1][y] = '+';
                }
                if(y != 0 &&maze[x][y-1] == '.'){
                    //查找左边
                    queue.offer(new int[]{x,y-1});
                    maze[x][y-1] = '+';
                }
                if(y != maze[0].length-1 &&maze[x][y+1] == '.'){
                    //查找右边
                    queue.offer(new int[]{x,y+1});
                    maze[x][y+1] = '+';
                }
            }
        }
        //找不到终点，返回-1
        result[0] = -1;
    }
    public boolean checkIsExit(char [][]maze,int x,int y){
        if(x == 0||y == 0 || x == maze.length-1||y == maze[0].length -1){
            return true;
        }
        return false;
    }
}
